package main

import "fmt"

/*
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：利用两个栈的辅助空间分别存储奇数偶数层的节点，然后打印输出。或使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出。
*/

type TreeNode struct {
	val       int
	leftNode  *TreeNode
	rightNode *TreeNode
}

func main() {
	//        8
	//       / \
	//      3   10
	//     /\   / \
	//    1  6     14
	//   /\  /\    /
	//      4  7  13
	root := TreeNode{val: 8}
	root.leftNode = &TreeNode{val: 3}
	root.rightNode = &TreeNode{val: 10}
	root.leftNode.leftNode = &TreeNode{val: 1}
	root.leftNode.rightNode = &TreeNode{val: 6}
	root.leftNode.rightNode.leftNode = &TreeNode{val: 4}
	root.leftNode.rightNode.rightNode = &TreeNode{val: 7}
	root.rightNode.rightNode = &TreeNode{val: 14}
	root.rightNode.rightNode.leftNode = &TreeNode{val: 13}

	printAsZ(&root)
}

func printAsZ(root *TreeNode) {
	if root == nil {
		return
	}

	var stack1 []*TreeNode
	var stack2 []*TreeNode

	stack1 = append(stack1, root)
	level := 1
	for len(stack1) != 0 || len(stack2) != 0 {
		// 奇数的时候
		if level%2 != 0 {
			var queue []int
			for len(stack1) != 0 {
				node := stack1[len(stack1)-1]
				stack1 = stack1[:len(stack1)-1]
				if node != nil {
					queue = append(queue, node.val)
					stack2 = append(stack2, node.leftNode)  // stack2代表的是偶数层，也就是这一层的下一层，
					stack2 = append(stack2, node.rightNode) // 输出的时候先右后左，所以要先将左节点压入栈中，这样输出的时候就可以先输出右节点
				}
			}
			if len(queue) != 0 {
				fmt.Println(queue)
				level++
			}
		} else {
			var queue []int
			for len(stack2) != 0 {
				node := stack2[len(stack2)-1]
				stack2 = stack2[:len(stack2)-1]
				if node != nil {
					queue = append(queue, node.val)
					stack1 = append(stack1, node.rightNode)
					stack1 = append(stack1, node.leftNode)
				}
			}
			if len(queue) != 0 {
				fmt.Println(queue)
				level++
			}
		}
	}
}
